
// 64.最小路径和
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        // DFS + 记忆法搜索
        int dx[] = {0 , 1};
        int dy[] = {1 , 0};

        int n = grid.size() , m = grid[0].size();
        vector<vector<int>> steps(n , vector<int>(m , -1));
        function<int(int,int)> dfs = [&](int x,  int y)
        {
            if(steps[x][y] != -1) return steps[x][y];
            if(x == n - 1 && y == m - 1) return grid[x][y];
            int ret = INT_MAX;
            for(int k = 0 ; k < 2 ; k++)
            {
                int a = x + dx[k] , b = y + dy[k];
                if(a < n && b < m) ret = min(ret , dfs(a , b) + grid[x][y]); 
            }
            steps[x][y] = ret;
            return ret;
        };
        return dfs(0 , 0);
    }
};